package h0908;
/**
  * @description 回文链表
  * @author 不知名帅哥
  * @date 2024/9/8 16:51
  * @version 1.0
*/
public class PalindromeList {
    public static void main(String[] args) {

    }

    static class ListNode {
        int val;
        ListNode next;

        public ListNode() {
        }

        public ListNode(int val) {
            this.val = val;
        }

        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
    public boolean isPalindrome(ListNode head) {
        if(head==null||head.next==null) return true;
        //定义快慢指针，反转后半部分链表
        ListNode slow=head;
        ListNode fast=head;
        while (fast.next!=null&&fast.next.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }

        //反转
        ListNode p=slow.next;
        ListNode q=p.next;
        while (q!=null){
            p.next=q.next;
            q.next=slow.next;
            slow.next=q;
            q=p.next;
        }
        //判断回文
        ListNode right_start=slow.next;
        while (right_start!=null){
            if (head.val!=right_start.val){
                return false;
            }
            head=head.next;
            right_start=right_start.next;
        }
        return true;
    }
}
